A Conditional Random Field for Discriminatively-trained Finite-state String Edit Distance

摘要

The need to measure sequence similarity arises in information extraction,object identity, data mining, biological sequence analysis, and other domains.This paper presents discriminative string-edit CRFs, a finitestate conditionalrandom field model for edit sequences between strings. Conditional randomfields have advantages over generative approaches to this problem, such as pairHMMs or the work of Ristad and Yianilos, because as conditionally-trainedmethods, they enable the use of complex, arbitrary actions and features of theinput strings. As in generative models, the training data does not have tospecify the edit sequences between the given string pairs. Unlike generativemodels, however, our model is trained on both positive and negative instancesof string pairs. We present positive experimental results on several data sets.